#include <stdlib.h>
#include <stdio.h>
#include "includes/myheap.h"

myheap *heap_create(size_t c, cmp_t cmp) {
    myheap *h = (myheap *) malloc(sizeof(myheap));
    void **d = (void **) malloc(sizeof(void *) * c);
    h->data = d;
    h->capacity = c;
    h->len = 0;
    h->cmp = cmp;
}

myheap *heap_create_arr(void **arr, size_t len, size_t c, cmp_t cmp) {
    myheap *h = (myheap *) malloc(sizeof(myheap));
    h->data = arr;
    h->capacity = c;
    h->len = len;
    h->cmp = cmp;
    heapify_all(h);
    return h;
}

void heap_insert(myheap *h, void* data) {
    if(heap_full(h)) {
        return;
    }
    h->data[h->len++] = data;
    int i = h->len - 1;
    // printf("heap insert i: %d, data: %d, parent: %d\n", i, *(int*)h->data[i], *(int*)h->data[HEAP_PARENT(i)]);
    while(i > 0 && h->cmp(h->data[HEAP_PARENT(i)], h->data[i]) > 0) {
        // printf("swap %d(%d) and %d(%d)\n", *(int*)h->data[i], i, *(int*)h->data[HEAP_PARENT(i)], HEAP_PARENT(i));
        swap(h->data, i, HEAP_PARENT(i));
        i = HEAP_PARENT(i);
    }
    // printf("insert data: %d, first data: %d\n", *(int *)data, *(int *)h->data[0]);
}

void heapify_all(myheap *h) {
    if(h->len > 0) {
        for (int i = (h->len - 2) / 2; i >= 0; i--)
        {
            // printf("heapify all loop %d start\n", i);
            heapify(h, i);
        }
        
    }
}

void heapify(myheap *h, int i) {
    void **data = h->data;
    int l = HEAP_LEFT_CHILD(i);
    int r = HEAP_RIGHT_CHILD(i);
    int minimum = i;
    if(l < h->len && h->cmp(data[l], data[minimum]) < 0){
        minimum = l;
    }
    if(r < h->len && h->cmp(data[r], data[minimum]) < 0){
        minimum = r;
    }
    if(minimum != i) {
        swap(data, i, minimum);
        heapify(h, minimum);
    }
}

void *heap_remove(myheap *h) {
    if(heap_empty(h)) return NULL;
    void *val = h->data[0];
    h->data[0] = h->data[--h->len];
    heapify(h, 0);
    return val;
}


void *heap_get(myheap *h) {
    if(heap_empty(h)) return NULL;
    return h->data[0];
}

int heap_full(myheap *h) {
    return h->len == h->capacity;
}

int heap_empty(myheap *h) {
    return h->len == 0;
}

void heap_sort(void **arr, size_t len, cmp_t cmp) {
    myheap *h = heap_create_arr(arr, len, len, cmp);
    for (int i = len - 1; i > 0; i--)
    {
        swap(arr, 0, i);
        h->len--;
        heapify(h, 0);
    }
    heap_destory(h, 0);
}


void heap_set(myheap *h, int i, void *val) {
    void *oldval = h->data[i];
    h->data[i] = val;
    if(h->cmp(val, oldval) < 0) {
        // printf("heap set val < oldval");
        while(i > 0 && h->cmp(h->data[HEAP_PARENT(i)], h->data[i]) > 0) {
            swap(h->data, i, HEAP_PARENT(i));
            i = HEAP_PARENT(i);
        }
    } else if(h->cmp(val, oldval) > 0) {
        // printf("heap set val > oldval");
        heapify(h, i);
    }
}

void heap_destory(myheap *h, int is_free_data) {
    // printf("heap destory");
    void **data = h->data;
    free(h);
    if(is_free_data) {
        free(data);
    }
}
